#include<iostream>
using namespace std;
class TreeNode {
public:
	char Data;
	TreeNode* left;
	TreeNode* right;
	TreeNode(char ch='#') {
		Data = ch;
		left = right = NULL;
	}
};
class Tree {
public:
	TreeNode* tmp;
	Tree() {
		tmp = CreateTree();
	}
	TreeNode* CreateTree() {
		char ch;
		cin >> ch;
		if (ch == '#') {
			return NULL;
		}
		TreeNode* p = new TreeNode;
		p->Data = ch;
		p->left = CreateTree();
		p->right = CreateTree();
		return p;
	}
	void change(TreeNode* p) {
		if (p != NULL) {
			TreeNode* tmp = p->left;
			p->left = p->right;
			p->right = tmp;
			change(p->left);
			change(p->right);
		}
	}
	void print_pre(TreeNode* p) {
		if (p != NULL) {
			cout << p->Data << ' ';
			print_pre(p->left);
			print_pre(p->right);
		}
	}
	void print_in(TreeNode* p) {
		if (p != NULL) {
			print_in(p->left);
			cout << p->Data << ' ';
			print_in(p->right);
		}
	}
	void print_post(TreeNode* p) {
		if (p != NULL) {
			print_post(p->left);
			print_post(p->right);
			cout << p->Data << ' ';
		}
	}
};
class QueueNode {
public:
	TreeNode* Data;
	QueueNode* next;
	QueueNode() {
	}
};
class Queue {
public:
	QueueNode* top;
	QueueNode* rear;
	Queue() {
		top = NULL;
		rear = NULL;
	}
	void Push(TreeNode* p) {
		if (top == NULL) {
			top = new QueueNode;
			top->Data = p;
			top->next = NULL;
			rear = top;
		}
		else {
			QueueNode* tmp = new QueueNode;
			tmp->Data = p;
			tmp->next = NULL;
			rear->next = tmp;
			rear = tmp;
		}
	}
	bool is() {
		return top == NULL;
	}
	void Pop() {
		if (!is()) {
			top = top->next;
			if (top == NULL) {
				rear = NULL;
			}
		}
	}
};
void print(TreeNode*p) {
	Queue q;
	q.Push(p);
	while (!q.is()) {
		cout << q.top->Data->Data << ' ';
		if (q.top->Data->left != NULL) {
			q.Push(q.top->Data->left);
		}
		if (q.top->Data->right != NULL) {
			q.Push(q.top->Data->right);
		}
		q.Pop();
	}
	cout << endl;
}
int main()
{
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		Tree t;
		t.change(t.tmp);
		if (t.tmp == NULL) {
			cout << "NULL" << endl;
			cout << "NULL" << endl;
			cout << "NULL" << endl;
			cout << "NULL" << endl;
		}
		else {
			t.print_pre(t.tmp);
			cout << endl;
			t.print_in(t.tmp);
			cout << endl;
			t.print_post(t.tmp);
			cout << endl;
			print(t.tmp);
		}
	}
	return 0;
}